package com.wyw.leetcode.learning.medium;

import java.util.LinkedList;
import java.util.Queue;

/**
 * leetcode topic 994
 *  腐烂的橘子
 *
 * @Author Mr Wu （yewen.wu.china@gmail.com）
 * @Date 2021/12/21 17:24
 */
public class Topic994 {

    private static int row;
    private static int col;
    private static int[][] vector = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    private int[][] grid;


    public static void main(String[] args) {
//        int mat[][] = new int[][] {{2,1,1}, {1,0,1}, {1,1,0}};
//        int mat[][] = new int[][] {{2,1,1}, {1,1,1}, {0,1,2}};
        int mat[][] = new int[][] {{0,1}};
//        System.out.println(orangesRotting(mat));
        System.out.println(orangesRotting1(mat));
    }


    public static int orangesRotting(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2) {
                    dfs(i, j, 2, grid); // 开始传染
                }
            }
        }

        // 经过dfs后，grid数组中记录了每个橘子被传染时的路径长度，找出最大的长度即为腐烂全部橘子所用的时间。
        int maxLevel = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    return -1; // 若有新鲜橘子未被传染到，直接返回-1
                } else {
                    maxLevel = Math.max(maxLevel, grid[i][j]);
                }
            }
        }

        return maxLevel == 0? 0: maxLevel - 2;
    }

    private static void dfs(int i, int j, int level, int[][] grid) { // level用来记录传染路径的长度（当然最后要减2）
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length ) {
            return;
        }
        if (grid[i][j] != 1 && grid[i][j] < level) { // 只有新鲜橘子或者传播路径比当前路径长的橘子，才继续进行传播。
            return;
        }

        grid[i][j] = level; // 将传染路径的长度存到grid[i][j]中
        level++;
        dfs(i - 1, j, level, grid);
        dfs(i + 1, j, level, grid);
        dfs(i, j - 1, level, grid);
        dfs(i, j + 1, level, grid);
    }

    /**
     * BFS
     */
    public static int orangesRotting1(int[][] grid) {

        if(grid == null || grid.length == 0) {
            return 0;
        }
        int row = grid.length;
        int col = grid[0].length;

        Queue<int[]> queue = new LinkedList<>();//腐烂新鲜橘子
        int cnt1 = 0;//新鲜橘子
        for(int i = 0; i< row; i++) {
            for(int j = 0; j< col; j++) {
                if(grid[i][j] == 2) {
                    queue.add(new int[]{i, j});
                } else if(grid[i][j] == 1) {
                    cnt1++;
                }
            }
        }

        int time = 0;
        while(!queue.isEmpty() && cnt1 > 0) {
            time++; // 一层一层的传染，每传染一层，时间+1
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] p = queue.poll();
                int x = p[0], y = p[1];
                if (x - 1 >= 0 && grid[x - 1][y] == 1) { // 上
                    cnt1--; // 每传染一个，更新新鲜橘子的数量
                    grid[x - 1][y] = 2;
                    queue.offer(new int[]{x - 1, y});
                }
                if (x + 1 < row && grid[x + 1][y] == 1) { // 下
                    cnt1--;
                    grid[x + 1][y] = 2;
                    queue.offer(new int[]{x + 1, y});
                }
                if (y - 1 >= 0 && grid[x][y - 1] == 1) { // 左
                    cnt1--;
                    grid[x][y - 1] = 2;
                    queue.offer(new int[]{x, y -1});
                }
                if (y + 1 < col && grid[x][y + 1] == 1) { // 右
                    cnt1--;
                    grid[x][y + 1] = 2;
                    queue.offer(new int[]{x, y +1});
                }
            }
        }
        return cnt1 == 0? time: -1;


    }
}
